package hot150;

// https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150
public class q5 {

    public int majorityElement(int[] nums) {
        return method1(nums, nums.length);
    }

    /**
     * 投票算法
     * 1 ms
     * 复杂度O(n)
     */
    public int method1(int[] nums, int n) {
        int cache = 0, count = 0;
        for (int num : nums) {
            // 由于众数超过一半，所以肯定有一个阈值下count会大于0，对应的数就是众数
            if (count == 0) {
                cache = num;
            }
            count += (num == cache ? 1 : -1);
        }
        return cache;
    }
}
